package array.elementRemove;

/**
 * @Author: 海琳琦
 * @Date: 2021/12/13 17:18
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * 请你设计时间复杂度为 O(n) 的算法解决本问题
 *
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 */
public class Title977 {
    public static void main(String[] args) {
        int[] nums = {-4, -1, 0, 3, 10};
        int[] ints = sortedSquares(nums);
        for (int a : ints) {
            System.out.println(a);
        }
    }

    private static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int leftIndex = 0, rightIndex = nums.length - 1, resultIndex = n - 1; leftIndex <= rightIndex; ) {
            if (-nums[leftIndex] > nums[rightIndex]) {
                result[resultIndex] = nums[leftIndex] * nums[leftIndex];
                leftIndex++;
            } else {
                result[resultIndex] = nums[rightIndex] * nums[rightIndex];
                rightIndex--;
            }
            resultIndex--;
        }
        return result;
    }
}
